package ca.compsci.opent.compiler.optimizer;

import java.util.List;

import ca.compsci.opent.compiler.analysis.*;
import ca.compsci.opent.compiler.node.*;
import ca.compsci.opent.compiler.semantics.*;

/**
 * The PostSemanticOptimizer has to be applied after the 
 * Semantic phase, but before the Code Generation phase.
 * 
 * This is necessary since it
 *  <ul>
 *     <li> Requires the SymbolTable provided by the SematicAnalyzer. </li>
 *     <li> Modifies the AST thus providing the optimisations. </li>
 *  </ul>
 * 
 * This class <em>(when completed)</em> performs the following optimisations:
 *  <ul>
 *     <li> Literal boolean negation evaluation </li>
 *     <li> Literal arithmetic negation evaluation </li>
 *     <li> Literal arithmetic evaluation </li>
 *     <li> Literal comparison evaluation </li>
 *     <li> Literal string concatenation evaluation </li>
 *     <li> Literal (boolean) and/or evaluation </li>
 *     <li> Dead code elimination </li>
 *     <ul>
 *          <li> Self assignment: a := a </li>
 *          <li> Unused local variables </li>
 *     </ul>
 *  </ul>
 * 
 * @author rizzix
 */

public class PostSemanticOptimizer extends DepthFirstAdapter {
	private SymbolTable scope;
	
	public PostSemanticOptimizer(SymbolTable table) {
		this.scope = table;
	}
	
	@Override
	public void inAInferDeclStmt(AInferDeclStmt node) {
		removeUnusedVariable(node.getIdentifier(), node.getRest());
		removeUnusedVariables(node.getRest());
		
		if (node.getIdentifier() == null)
			node.replaceBy(null);
	}

	@Override
	public void inAInferInitStmt(AInferInitStmt node) {
		removeUnusedVariable(node.getIdentifier(), node.getRest());
		removeUnusedVariables(node.getRest());
		
		if (node.getIdentifier() == null)
			node.replaceBy(null);
	}

	@Override
	public void inATypedDeclStmt(ATypedDeclStmt node) {
		removeUnusedVariable(node.getIdentifier(), node.getRest());
		removeUnusedVariables(node.getRest());
		
		if (node.getIdentifier() == null)
			node.replaceBy(null);
	}

	@Override
	public void inATypedInitStmt(ATypedInitStmt node) {
		removeUnusedVariable(node.getIdentifier(), node.getRest());
		removeUnusedVariables(node.getRest());
		
		if (node.getIdentifier() == null)
			node.replaceBy(null);
	}

	// Account for sub-scopes.
	@Override
	public void caseABlockStmt(ABlockStmt node) {
		SymbolTable current_scope = scope;
		scope = current_scope.newSubScope();
		super.caseABlockStmt(node);
		scope = current_scope;
	}

	// Attempts to perform some compile time evaluations on certain expressions.
	@Override
	public void outABinOprExpr(ABinOprExpr node) {		
		Expression expr = (Expression) scope.getInfo(SemanticAnalyzer.mkABinOprExprKey(node));
		
		PExpr left = node.getLeft(), right = node.getRight();
		
		if (left instanceof ANumberExpr && right instanceof ANumberExpr) {
			Literal left_num = (Literal) scope.getInfo(SemanticAnalyzer.mkANumberExprKey((ANumberExpr)left));
			Literal right_num = (Literal) scope.getInfo(SemanticAnalyzer.mkANumberExprKey((ANumberExpr)right));
			
			ArithmeticEvaluator evaluator = new ArithmeticEvaluator(left_num, right_num, expr.getPromotedType());
			node.getOpr().apply(evaluator);
			
			String literal = evaluator.result().toString();
			
			ANumberExpr numexpr = new ANumberExpr(new TNumericLit(literal));
			
			scope.remove(SemanticAnalyzer.mkANumberExprKey((ANumberExpr)left));
			scope.remove(SemanticAnalyzer.mkANumberExprKey((ANumberExpr)right));
			scope.remove(SemanticAnalyzer.mkABinOprExprKey(node));
			
			node.replaceBy(numexpr);
			
			//XXX: currently assumes the evaluator.resultantType()
			//     is the same as that of expr.getType() (i.e the expression's
			//     expected resultant type).
			scope.add(SemanticAnalyzer.mkANumberExprKey(numexpr),
					new Literal(evaluator.resultantType(), evaluator.result()));
		}
		
		if (left instanceof ABooleanExpr && right instanceof ABooleanExpr) {
			Literal left_bool = (Literal) scope.getInfo(SemanticAnalyzer.mkABooleanExprKey((ABooleanExpr)left));
			Literal right_bool = (Literal) scope.getInfo(SemanticAnalyzer.mkABooleanExprKey((ABooleanExpr)right));
			
			BooleanEvaluator evaluator = new BooleanEvaluator(left_bool, right_bool);
			node.getOpr().apply(evaluator);
			
			ABooleanExpr boolexpr;
			
			if (evaluator.result())
				boolexpr = new ABooleanExpr(new TBooleanLit(Literal.TRUE));
			else
				boolexpr = new ABooleanExpr(new TBooleanLit(Literal.FALSE));
			
			scope.remove(SemanticAnalyzer.mkABinOprExprKey(node));
			
			node.replaceBy(boolexpr);
			
			scope.add(SemanticAnalyzer.mkABooleanExprKey(boolexpr),
					new Literal(evaluator.resultantType(), evaluator.result()));
		}
	}
	
	// Eliminate unused variables' lvalue (assignment) _statements_
	@Override
	public void outAAssignExpr(AAssignExpr node) {
		if (isUnusedVariable(node.getIdentifier()))
			node.replaceBy(node.getExpr());
	}

	
	// Helper functions...

	private void removeUnusedVariable(TIdentifier first, List<TIdentifier> rest) {
		if (isUnusedVariable(first)) {
			String key = SemanticAnalyzer.mkTIdentifierKey(first);
			first.replaceBy(findFirstUsedVariable(rest, 0));
			scope.remove(key);
		}
	}

	// XXX: O(n^2) algorithm. It can be improved. 
    // For most cases the penalty would be insignificant since
	// `n` is usually a very small number
	private void removeUnusedVariables(List<TIdentifier> rest) {
		for (int i = 0; i < rest.size(); i++) {
			TIdentifier id = rest.get(i);
			if (isUnusedVariable(id)) {
				String key = SemanticAnalyzer.mkTIdentifierKey(id);
				id.replaceBy(findFirstUsedVariable(rest, 1 + i--));
				scope.remove(key);
			}
		}
	}
	
	private boolean isUnusedVariable(TIdentifier t) {
		Variable v = (Variable) scope.getInfo(SemanticAnalyzer.mkTIdentifierKey(t));
		
		// the v == null is necessary, since it's possible that the unused
		// variable `t` has been removed from the symbol table already.
		return  v == null || !v.wasUsedAsRValue();
	}
	
	private TIdentifier findFirstUsedVariable(List<TIdentifier> rest, int offset) {
		for (int i = offset; i < rest.size(); i++) {
			TIdentifier id = rest.get(i);
			if (!isUnusedVariable(id)) {
				id.replaceBy(null); 
				return id;
			}
		}
		return null;
	}
}
